# 并查集
class DSU:
    def __init__(self, n: int):
        self.s = [i for i in range(n + 1)]
        self.h = [0] * (n + 1)

    def find(self, u: int) -> int:
        if u != self.s[u]:
            self.s[u] = self.find(self.s[u])
        return self.s[u]

    def merge(self, u: int, v: int) -> bool:
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return False
        if self.h[u] > self.h[v]:
            u, v = v, u
        if self.h[u] == self.h[v]:
            self.h[v] += 1
        self.s[u] = v
        return True


# 欧拉路
class Euler:
    def __init__(self, n: int, edges: dict):
        self.n = n
        self.edges = edges

    def getPath(self) -> list:
        if self.allConnect():
            start = self.isEulerGraph()
            if start != -1:
                return self.findPath(start)
        return []

    def allConnect(self) -> bool:
        dsu = DSU(self.n)
        for u, val in self.edges.items():
            for v in val:
                dsu.merge(u, v)
        return len(set(dsu.find(node) for node in self.edges.keys())) == 1

    # return the start node if it is an euler graph else -1
    def isEulerGraph(self) -> int:
        start = -1
        cnt = 0  # 奇数度数点的个数
        keys = sorted([*self.edges.keys()])
        for u in keys:
            if len(self.edges[u]) & 1:
                if start == -1:
                    start = u
                cnt += 1
        if start == -1:
            start = keys[0]
        return start if cnt == 0 or cnt == 2 else -1

    def findPath(self, start) -> list:
        path = []
        edges = self.edges

        def dfs(u: int):
            while len(edges[u]) > 0:
                v = edges[u].pop()
                edges[v].remove(u)
                dfs(v)
            path.append(u)
        dfs(start)
        return path[::-1]